Décomposition en facteurs premiers et PGCD

Propriété

Soit \(m\) et \(n\) deux entiers supérieurs ou égaux à \(2\) . On suppose, quitte à utiliser des exposants nuls, que \(m\) et \(n\) se décomposent en produits de facteurs premiers sous la forme :

\(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\)    et    \(m=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}\) .

On a alors :  \(\mathrm{PGCD}(n;m)=p_1^{\min(\alpha_1;\beta_1)}p_2^{\min(\alpha_2;\beta_2)}...p_k^{\min(\alpha_k;\beta_k)}\) .

Démonstration

Soit \(d\) un diviseur commun à \(n\) et \(m\) . Alors 
\(d=p_1^{\gamma_1}p_2^{\gamma_2}...p_k^{\gamma_k}\)  avec, pour tout \(i \in \left\lbrace 1;...;k \right\rbrace\) , \(\left\lbrace\begin{array}{l}0 \leqslant \gamma_i \leqslant \alpha_i\\ 0 \leqslant \gamma_i \leqslant \beta_i\end{array} \right.\)  
autrement dit \(0 \leqslant \gamma_i \leqslant \min(\alpha_i;\beta_i)\) .

La plus grande valeur possible pour \(d\) , qui est le PGCD de \(n\) et \(m\) , est donc bien 
\(\mathrm{PGCD}(n;m)=p_1^{\min(\alpha_1;\beta_1)}p_2^{\min(\alpha_2;\beta_2)}...p_k^{\min(\alpha_k;\beta_k)}\) .